package 剑指offer.递归与回溯;

/**
 * 和 12 题不同的是本题要求从 (0, 0) 进入而非任意一个位置
 *
 * 依然是回溯法
 */
public class 第13题机器人的运动范围 {

    /**
     *
     * @param m 矩阵行数
     * @param n 矩阵列数
     * @param k 阈值
     * @param i 当前遍历的行
     * @param j 当前遍历的列
     * @param visited 记录走过的格子
     * @return
     */
    public static int howMuchAttain(int m, int n, int k, int i, int j, boolean[][] visited) {
        int count = 0;

        if (check(m, n, i, j, k, visited)) {
            visited[i][j] = true;
            count = 1 + howMuchAttain(m, n, k, i, j + 1, visited)
                    + howMuchAttain(m, n, k, i, j - 1, visited)
                    + howMuchAttain(m, n, k, i + 1, j, visited)
                    + howMuchAttain(m, n, k, i - 1, j, visited);
        }

        return count;
    }

    private static boolean check(int m, int n, int i, int j, int k, boolean[][] visited) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] == true || getSum(i, j) > k)
            return false;
        return true;
    }

    private static int getSum(int i, int j) {
        return sum(i) + sum(j);
    }

    private static int sum(int x) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        int m = 3;
        int n = 3;
        int k = 3;
        int i = 0;
        int j = 0;
        boolean[][] visited = new boolean[m][n];
        System.out.println(howMuchAttain(m, n, k, i, j, visited));
    }
}
